package 回溯算法;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author: biubiu0002
 * @Date: 2021-03-25 16:21
 **/
public class 子集 {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
        LinkedList<Integer> trace = new LinkedList<>();

        backtrace(nums,0,trace);

        return res;



    }

    //路径
    //选择
    //base case
    //维护start下标 来排除start索引之前的数字
    //保证集合按照数组的升序排序。
    public void backtrace(int[] nums,int start,LinkedList<Integer> trace){
        //base case
        res.add(new LinkedList<>(trace));


        for(int i=start;i<nums.length;i++){
            //排除不合法选择
            if(!isValid(trace,nums,i)){
                continue;
            }
            //做选择
            trace.add(nums[i]);
            //下一层
            backtrace(nums,i+1, trace);
            //撤销选择
            trace.removeLast();

        }

    }

    public boolean isValid(LinkedList<Integer> trace,int[]nums,int i){
        if(trace.contains(nums[i]))
            return false;
        return true;
    }



    public static void main(String[] args) {
        int[] nums = {1,2,3};
        子集 c = new 子集();
        System.out.println(c.subsets(nums));


    }
}
